typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

bool QueEmpty(Que* pq)
{
	assert(pq);
	return pq->head == NULL;
}
void QueInit(Que* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

void QueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QuePop(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

QDataType QueFront(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->head->data;
}

QDataType QueBack(Que* pq)
{
	assert(pq);
	assert(!QueEmpty(pq));
	return pq->tail->data;
}

int QueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}



typedef struct
{
	Que q1;
	Que q2;
} MyStack;


MyStack* myStackCreate()
{
	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	QueInit(&st->q1);
	QueInit(&st->q2);
	return st;
}

void myStackPush(MyStack* obj, QDataType x)
{
	if (!QueEmpty(&obj->q1))
	{
		QuePush(&obj->q1, x);
	}
	else
	{
		QuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj)
{
	Que* empty = &obj->q1;
	Que* noempty = &obj->q2;
	if (!QueEmpty(&obj->q1))
	{
		empty = &obj->q2;
		noempty = &obj->q1;
	}
	while (QueSize(noempty) > 1)
	{
		QuePush(empty, QueFront(noempty));
		QuePop(noempty);
	}
	int top = QueFront(noempty);
	QueFront(noempty);
	return top;
}

int myStackTop(MyStack* obj)
{
	if (!QueEmpty(&obj->q1))
	{
		return QueBack(&obj->q1);
	}
	else
	{
		return QueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj)
{
	return QueEmpty(&obj->q1) && QueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
	QueDestroy(&obj->q1);
	QueDestroy(&obj->q2);
	free(obj);
}